848. Shifting Letters

https://leetcode.com/problems/shifting-letters/

題目解釋

你有一個字串都是小寫的字串s ，還有一組偏移(shift)次數的陣列shifts

一次的shift 會將字母往下一個順序偏移，如 shift('a') = 'b', shift('t') = 'u', shift('z') = 'a'

而陣列shifts[i] = x 代表我們要將字串s 的前i+1 個字母偏移x 次

example

解法:

1. 首先，這題要把字母做變化的話，用ASCII的代碼做計算應該是最方便的

2. 再來，我們要計算各個字母需要偏移幾次，如example1 的a 是17次、b 是14次、c 是9次

3. 最後，我們計算字串s的每個字母，記錄他已經從字母a 偏移幾次了，如a 偏移0次、b偏移1次、c偏移2次，這樣比較方便計算

4. 最後的最後，我們就得到Time Limit Exceeded 的程式碼

程式碼

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        
        s_int = [ord(i) - 97 for i in s] #記錄從字母*a* 偏移幾次了
        
        shifts_sum = [sum(shifts[i:]) for i in range(len(shifts))] # 計算各個字母需要偏移幾次
        
        res = ''
        for i in range(len(s)):
            res += chr(97 + (s_int[i] + shifts_sum[i]) % 26) #別忘了modulo 26
            
        return res

可以過得解法:

LeetCode的很多題目若送出O(n^2)的解答通常就不會過

而上段程式碼的shifts_sum = [sum(shifts[i:]) for i in range(len(shifts))] 就是太花時間的原因，所以我們稍微改一下第二步的想法

example1 的a 要偏移17次，也就是3 + 5 + 9次
example1 的b 要偏移 8次，也就是 5 + 9次
example1 的c 要偏移 9次，也就是 9次

依照上面的規律，我們只需要先把shifts 做加總，再一項一項扣除掉不需要的次數就好

程式碼

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        
        s_int = [ord(i) - 97 for i in s]
        
        shifts_sum = sum(shifts)

        res = ''
        for i in range(len(s)):
            res += chr(97 + (s_int[i] + shifts_sum) % 26)
            shifts_sum -= shifts[i]
            
        return res

閒聊

今天的題目是難度Medium 的題目，寫起來不會很難

就只要多想一下怎麼避免迴圈包住迴圈的解法而已

今天是第8天，恭喜我自己完成一周的進度囉!